题解 CF570E 【Pig and Palindromes】

发表于 | 更新于

题意:给定一个由小写字母组成的$n \times m$的矩阵 $A$，求从$A_{1, 1}$到$A_{n, m}$的所有路径中，回文串的个数。途中只能向下或向右走一格。

感觉有点像传纸条，传纸条是是维护两个点同时从起点出发，保证步数相同，转移到终点，这道题是一个点从起点，另一个点从终点出发，保证步数相同$f[step][i][j][k][p]$表示走了$step$步，一个点走到$(i,j),$另一个点走到$(k,p)$，但是这样的状态在时空复杂度上都过不去，所以我们要优化，于是我们发现$j$和$p$都可以通过$step$算出来，并且我们可以滚动数组存储$step$这一位，并且在细节处理上这道题还是挺麻烦的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
#define base 131
#define mod 1000000007
#define ll long long
using namespace std;
int dx[]={-1,-1,0,0},dy[]{1,0,1,0},f[2][1000][1000];
char s[1000][1000];
int main(){
    int n=read(),m=read();
    for (int i=1;i<=n;++i)    
        scanf("%s",s[i]+1);
    if (s[1][1]!=s[n][m]){
        puts("0");
        return 0;
    }
    f[1][1][n]=1;
    int now=1;
    for (int st=2;st<=(n+m)>>1;++st){
        now^=1;
        memset(f[now],0,sizeof(f[now]));
        for (int i=1;i<=min(st,n);++i)
            for (int k=n;k>=max(n-st,i);--k){
                int j=st-i+1,p=m-(st-(n-k))+1;
                if (s[i][j]==s[k][p])
                    for (int t=0;t<4;++t)
                        f[now][i][k]=(f[now][i][k]+f[now^1][i+dx[t]][k+dy[t]])%mod;//左边的点可以由左与上转移过来，右边的点可以由右与下转移过来
            }
    }
    ll ans=0;
    if ((n+m)&1)
        for (int i=1;i<=n;++i)
            ans=(ans+f[now][i][i]+f[now][i][i+1])%mod;
    else 
        for (int i=1;i<=n;++i)
            ans=(ans+f[now][i][i])%mod;//n与m的奇偶性需要特判
    printf("%d",ans);
}